package com.leetcode;
/**
 * 31 下一个排序
 * 思路:
 *      从后面 向前找 找到逆序的 记录下来
 *      从后面 向前找 找到记录较大的  交换位置
 *      在记录位置之后的 所有数据进行 重排序
 */

import java.util.Arrays;

public class D_31 {

    public static void main(String[] args) {
//        int[] nums = {1, 2, 3};  1,3,2
//        int[] nums = {1, 3, 2};  [2, 3, 1]
//        int[] nums = {2, 3, 1}; 3, 1, 2
//        int[] nums = {3, 1, 2};  3, 2, 1
//        int[] nums = {3, 2, 1};  [1, 2, 3]
        int[] nums = {1, 2, 3};

        new D_31().nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void nextPermutation(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i - 1] < nums[i]) {
//                小于以后
                for (int j = nums.length - 1; j > i-1; j--) {
                    if (nums[i - 1] < nums[j]) {
//                        记录 i-1 j 互换
                        int temp = nums[i - 1];
                        nums[i - 1] = nums[j];
                        nums[j] = temp;

//                      i 到 nums.length - 1 重新排序
                        Arrays.sort(nums, i, nums.length);
                        return;
                    }
                }
//                如果没有比自己小的
            }
        }
        Arrays.sort(nums);
    }
}
